//
// Created by Administrator on 2021/8/2.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>

using namespace std;

class Solution {
public:
    void setZeroes(vector<vector<int>> &matrix) {
        // 如果发现一个单元格为0，那么标记它所在行、列的第一个元素为0，不需要马上进行置0，遍历完成后置一次就行
        auto m = matrix.size(), n = matrix[0].size();
        vector<int> row(m, 1), col(n, 1);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    row[i] = 0;
                    col[j] = 0;
                }
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (row[i] == 0 or col[j] == 0)
                    matrix[i][j] = 0;
            }
        }
    }
};

class Solution2 {
public:
    void setZeroes(vector<vector<int>> &matrix) {
        int m = (int) matrix.size();
        int n = (int) matrix[0].size();
        int flag_col0 = false, flag_row0 = false;
        // 第一列是否含0
        for (int i = 0; i < m; i++) {
            if (!matrix[i][0]) {
                flag_col0 = true;
            }
        }
        // 第一行是否含0
        for (int j = 0; j < n; j++) {
            if (!matrix[0][j]) {
                flag_row0 = true;
            }
        }
        // 用其余的行 列 更新第一行 第一列
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (!matrix[i][j]) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        // 根据第一行、第一列的数据，更新其余行、列
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (!matrix[i][0] || !matrix[0][j]) {
                    matrix[i][j] = 0;
                }
            }
        }
        // 第一行  第一列最后处理
        if (flag_col0) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        if (flag_row0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
    }
};

class Solution3 { // 只用一个额外变量
public:
    void setZeroes(vector<vector<int>> &matrix) {
        int m = (int) matrix.size();
        int n = (int) matrix[0].size();
        int flag_col0 = false;
        for (int i = 0; i < m; i++) {
            if (!matrix[i][0]) {
                flag_col0 = true;
            }
            for (int j = 1; j < n; j++) {
                if (!matrix[i][j]) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 1; j < n; j++) {
                if (!matrix[i][0] || !matrix[0][j]) {
                    matrix[i][j] = 0;
                }
            }
            if (flag_col0) {
                matrix[i][0] = 0;
            }
        }
    }
};

int main() {
    vector<vector<int>> matrix{{0, 1, 2, 0},
                               {3, 4, 5, 2},
                               {1, 3, 1, 5}};
    vector<vector<int>> mat2{{1,  2,  3,  4},
                             {5,  0,  7,  8},
                             {0,  10, 11, 12},
                             {13, 14, 15, 0}};
    Solution solution;
    solution.setZeroes(mat2);
    for (auto &x:mat2) {
        for (auto &y:x) {
            cout << y;
            cout << " ";
        }
        cout << endl;
    }
    return 0;
}
